package backtrackStudy;

import java.util.LinkedList;
import java.util.List;

public class CombinationSum {

    private List<List<Integer>> ans = new LinkedList<>();

    /**
     * LeetCode T39 组合总数
     * 组合问题——组合总数
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，
     * 找出 candidates 中所有可以使数字和为 target 的组合。
     * @param args
     */
    public static void main(String[] args) {

    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //记录路径结果
        LinkedList<Integer> trace = new LinkedList<>();
        backtrace(candidates, 0, target, trace);
        return ans;
    }

    public void backtrace(int[] candidates, int beginIndex, int target, LinkedList<Integer> trace){
        if (target == 0){
            ans.add(new LinkedList<>(trace));
            return;
        }
        for (int i = beginIndex; i < candidates.length; i++){
            if (target - candidates[i] >= 0){
                trace.add(candidates[i]);
                backtrace(candidates, i, target - candidates[i], trace);
                trace.removeLast();
            }
        }
    }

}
